package heap;

import array.Array;

public class MaxHeap <E extends Comparable<E>> {
    private Array<E> data;

    public MaxHeap(int size){
        data = new Array<>(size);
    }

    public MaxHeap(){
        data = new Array<>();
    }

    //返回完全二叉树的数组中一个索引所表示的元素的父亲节点的索引
    private int parent(int index){
        if(index == 0)
            throw new IllegalArgumentException("index");
        return (index - 1) / 2;
    }

    //返回堆中的元素个数
    public int size(){
        return data.getSize();
    }

    //返回一个布尔值，表示堆中是否为空
    public boolean isEmpty(){
        return data.isEmpty();
    }

    //返回完全二叉树的数组表示中一个索引所表示的元素的左孩子节点的索引。
    private int leftChild(int index){
        return 2*index + 1;
    }

    //返回完全二叉树的数组表示中一个索引所表示的右孩子节点的索引。
    private int rightChild(int index){
        return 2*index + 2;
    }

    //向堆中添加元素和sift up（上浮）
    public void add(E e){
        data.addLast(e);
        int k = data.getSize() - 1;
        siftUp(k);
    }

    private void siftUp(int k){
        while( k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0){
            data.swap(k,parent(k));
            k = parent(k);
        }
    }

    //从堆中取出元素和sift down
    public E extractMax(){
        E ret = data.getFirst();

        data.swap(0,data.getSize() - 1);

        //删除最后一个元素
        data.removeLast();

        //sift down
        siftDown(0);

        return ret;
    }


    private void siftDown(int k){

        while(leftChild(k) < data.getSize()){
            //已经查到底了
            int j = leftChild(k);//拿到左孩子节点
            if(j+1 >= data.getSize())
                break;
            if(data.get(j).compareTo(data.get(j+1)) < 0)
                j = j+1;
            if(data.get(k).compareTo(data.get(j)) > 0)
                break;
            if(data.get(k).compareTo(data.get(j)) < 0)
                data.swap(k,j);
            k = j;
        }
    }
}
